package com.zs.letcode.illustration_of_algorithm;

import java.util.HashMap;
import java.util.Map;

/**
 * 剑指 Offer 48. 最长不含重复字符的子字符串
 * 请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。
 * <p>
 * <p>
 * 示例1:
 * <p>
 * 输入: "abcabcbb"
 * 输出: 3
 * 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
 * 示例 2:
 * <p>
 * 输入: "bbbbb"
 * 输出: 1
 * 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
 * 示例 3:
 * <p>
 * 输入: "pwwkew"
 * 输出: 3
 * 解释: 因为无重复字符的最长子串是"wke"，所以其长度为 3。
 * 请注意，你的答案必须是 子串 的长度，"pwke"是一个子序列，不是子串。
 * <p>
 * 提示：
 * <p>
 * s.length <= 40000
 * 注意：本题与主站 3 题相同：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/
 * <p>
 * 相关标签
 * 哈希表
 * 字符串
 * 滑动窗口
 * <p>
 * Python3
 * <p>
 * <p>
 * <p>
 * 作者：Krahets
 * 链接：https://leetcode-cn.com/leetbook/read/illustration-of-algorithm/5dgr0c/
 * 来源：力扣（LeetCode）
 * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 *
 * @author madison
 * @description
 * @date 2021/8/13 12:23
 */
public class Chapter18 {
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.lengthOfLongestSubstring3("abcabcbb"));//3
        System.out.println(solution.lengthOfLongestSubstring("pwwkew"));//3
        System.out.println(solution.lengthOfLongestSubstring("bbbbb"));//1
    }

    private static class Solution {
        public int lengthOfLongestSubstring(String s) {
            int slow = 0;
            int maxLen = 1;
            while (slow < s.length()) {
                int fast = slow + 1;
                if (fast == s.length()) {
                    return maxLen;
                }
                while (fast < s.length() && s.substring(slow, fast).contains(s.charAt(fast + 1) + "")) {
                    maxLen = Math.max(maxLen, fast - slow + 1);
                    fast++;
                }
                slow++;
            }
            return maxLen;
        }

        /**
         * 方法一：动态规划 + 哈希表
         */
        public int lengthOfLongestSubstring1(String s) {
            Map<Character, Integer> dic = new HashMap<>();
            int res = 0, tmp = 0, len = s.length();
            for (int i = 0; i < len; i++) {
                int j = dic.getOrDefault(s.charAt(i), -1);
                dic.put(s.charAt(i), i);
                tmp = tmp < i - j ? tmp + 1 : i - j;
                res = Math.max(res, tmp);
            }
            return res;
        }

        /**
         * 方法二： 动态规划 + 线性遍历
         */
        public int lengthOfLongestSubstring2(String s) {
            int res = 0, tmp = 0, len = s.length();
            for (int j = 0; j < len; j++) {
                int i = j - 1;
                while (i >= 0 && s.charAt(i) != s.charAt(j)) i--;
                tmp = tmp < j - i ? tmp + 1 : j - i;
                res = Math.max(res, tmp);
            }
            return res;
        }

        /**
         * 方法三：双指针 + 哈希表
         */
        public int lengthOfLongestSubstring3(String s) {
            Map<Character, Integer> dic = new HashMap<>();
            int i = -1, res = 0, len = s.length();
            for (int j = 0; j < len; j++) {
                if (dic.containsKey(s.charAt(j))) {
                    i = Math.max(i, dic.get(s.charAt(j)));
                }
                dic.put(s.charAt(j), j);
                res = Math.max(res, j - i);
            }
            return res;
        }
    }
}
